package jianzhiOffer;
//剑指 Offer 07. 重建二叉树
import java.util.HashMap;
import java.util.Map;

public class Num07_buildTree {
    private Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
        //边界条件
        if (preorder_left > preorder_right){
            return null;
        }
        //前序遍历的第一个节点就是根节点
        int preorder_root = preorder_left;
        //在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        //创建根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //算出左子树的节点个数
        int size_left_subtree = inorder_root - inorder_left;
        //递归构造左子树，并连接根节点
        root.left = myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);
        //递归构造右子树，并连接根节点
        root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);
        return root;
    }

}
